package com.dycong.common.leetcode;

/**
 * @author dycong
 * @date 2019/9/25 12:32
 * 这个题如果没有星号，那么问题就很简单，直接挨个从左到右比较看是否匹配就可以。有星号的情况我们必须进行回溯，在回溯过程中。
 * 1.如果第一个字符不匹配，那么只有一种情况可以匹配上，就是出现了星号，而且剩下的字符可以匹配上，举个例子：
 */
public class RegMatch_10 {

    public static void main(String[] args) {
        System.out.println(isMatch2("ab", ".a*"));;
        System.out.println(isMatch("ab", ".a*"));;
    }

    public static boolean isMatch2(String s, String p) {
        if (p.isEmpty()) return s.isEmpty();

        if (s.isEmpty()) {
            return p.charAt(1) == '*' && p.length() == 2;
        }

        char[] sArray = s.toCharArray();
        char[] pArray = p.toCharArray();
        int i = 0, j = 0;
        char pc = pArray[j];

        for (; i < sArray.length; i++) {
            char sc = sArray[i];

            if (sc == pc || pc == '.') {
                pc = pArray[++j];
                continue;
            }else if (pc == '*'){
                if (sc == pArray[j-1]){
                    continue;
                }else {
                    return false;
                }
            }
            //!=
            pc = pArray[++j];
            if (pc != '*') {
                return false;
            } else {
                pc = pArray[++j];
            }
        }

        return true;
    }


    public static boolean isMatch(String text, String pattern) {
        if (pattern.isEmpty()) return text.isEmpty();
        //第一个是否匹配上
        boolean first_match = (!text.isEmpty() &&
                (pattern.charAt(0) == text.charAt(0) || pattern.charAt(0) == '.'));

        if (pattern.length() >= 2 && pattern.charAt(1) == '*') {
            //看有没有可能,剩下的pattern匹配上全部的text
            //看有没有可能,剩下的text匹配整个pattern
            return (isMatch(text, pattern.substring(2)) ||
                    (first_match && isMatch(text.substring(1), pattern)));

        } else {
            //没有星星的情况:第一个字符相等,而且剩下的text,匹配上剩下的pattern
            return first_match && isMatch(text.substring(1), pattern.substring(1));
        }
    }
}
